
<!DOCTYPE html>
<html lang="zh-CN" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>leetcode1368. 使网格图至少有一条有效路径的最小代价 - peony&#39;s blogs</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="peony,"> 
    <meta name="description" content="leetcode1368. 使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i],"> 
    <meta name="author" content="peony"> 
    <link rel="alternative" href="atom.xml" title="peony&#39;s blogs" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon63.png"> 
    
<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">

    
<link rel="stylesheet" href="/css/diaspora.css">

    <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
    <script>
         (adsbygoogle = window.adsbygoogle || []).push({
              google_ad_client: "ca-pub-8691406134231910",
              enable_page_level_ads: true
         });
    </script>
    <script async custom-element="amp-auto-ads"
        src="https://cdn.ampproject.org/v0/amp-auto-ads-0.1.js">
    </script>
<meta name="generator" content="Hexo 4.2.0"></head>

<body class="loading">
    <span id="config-title" style="display:none">peony&#39;s blogs</span>
    <div id="loader"></div>
    <div id="single">
    <div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <a class="icon-home image-icon" href="javascript:;" data-url="http://yoursite.com"></a>
    <div title="播放/暂停" class="icon-play"></div>
    <h3 class="subtitle">leetcode1368. 使网格图至少有一条有效路径的最小代价</h3>
    <div class="social">
        <!--<div class="like-icon">-->
            <!--<a href="javascript:;" class="likeThis active"><span class="icon-like"></span><span class="count">76</span></a>-->
        <!--</div>-->
        <div>
            <div class="share">
                <!--<a title="获取二维码" class="icon-scan" href="javascript:;" ></a>-->
            </div>
            <div id="qr"></div>
        </div>
    </div>
    <div class="scrollbar"></div>
</div>

    <div class="section">
        <div class="article">
    <div class='main'>
        <h1 class="title">leetcode1368. 使网格图至少有一条有效路径的最小代价</h1>
        <div class="stuff">
            <span>三月 14, 2020</span>
            

        </div>
        <div class="content markdown">
            <h1 id="leetcode1368-使网格图至少有一条有效路径的最小代价"><a href="#leetcode1368-使网格图至少有一条有效路径的最小代价" class="headerlink" title="leetcode1368. 使网格图至少有一条有效路径的最小代价"></a>leetcode1368. 使网格图至少有一条有效路径的最小代价</h1><hr>
<blockquote>
<p>给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：</p>
</blockquote>
<blockquote>
<ul>
<li>1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]</li>
<li>2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]</li>
<li>3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]</li>
<li>4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]<br>注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。</li>
</ul>
</blockquote>
<blockquote>
<p>一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。</p>
</blockquote>
<blockquote>
<p>你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。</p>
</blockquote>
<blockquote>
<p>请你返回让网格图至少有一条有效路径的最小代价。</p>
</blockquote>
<blockquote>
<p>示例 1：</p>
</blockquote>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDIwLzAyLzI5L2dyaWQxLnBuZw?x-oss-process=image/format,png" alt="在这里插入图片描述"></p>
<blockquote>
<p>输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]<br>输出：3<br>解释：你将从点 (0, 0) 出发。<br>到达 (3, 3) 的路径为： (0, 0) –&gt; (0, 1) –&gt; (0, 2) –&gt; (0, 3) 花费代价 cost = 1 使方向向下 –&gt; (1, 3) –&gt; (1, 2) –&gt; (1, 1) –&gt; (1, 0) 花费代价 cost = 1 使方向向下 –&gt; (2, 0) –&gt; (2, 1) –&gt; (2, 2) –&gt; (2, 3) 花费代价 cost = 1 使方向向下 –&gt; (3, 3)<br>总花费为 cost = 3.</p>
</blockquote>
<p>我看了一下他的题解：<a href="https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/zui-duan-lu-jing-suan-fa-bfs0-1bfsdijkstra-by-luci/" target="_blank" rel="noopener">最短路径算法</a>，写出了我的理解。因为之前没怎么做过图的题，所以写的很详细，基本上每一行都有注释。大概思路为：bfs搜索，更新每个节点花费的cost值，然后每次只选取花费最小cost的方向，这样最后花费的cost最小。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minCost</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>&#123;</span><br><span class="line">        Queue&lt;<span class="keyword">int</span>[]&gt;queue=<span class="keyword">new</span> LinkedList();<span class="comment">//，每个queue元素是[x,y]</span></span><br><span class="line">        <span class="keyword">int</span>[][]direction=&#123;&#123;<span class="number">0</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;,&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;&#125;;</span><br><span class="line">        <span class="comment">//四个方向有五个是因为为了和题里面的1,2,3,4四个编号匹配上</span></span><br><span class="line">        queue.add(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;<span class="number">0</span>,<span class="number">0</span>&#125;);<span class="comment">//把初始位置加进去</span></span><br><span class="line">        <span class="keyword">int</span>[][]count=<span class="keyword">new</span> <span class="keyword">int</span>[grid.length][grid[<span class="number">0</span>].length];<span class="comment">//记录每个节点的cost花费情况</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;count.length;i++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;count[i].length;j++)</span><br><span class="line">                count[i][j]=Integer.MAX_VALUE;</span><br><span class="line">                <span class="comment">//赋值为最大值，因为下面的cost要比当前的值小才能更新</span></span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        count[<span class="number">0</span>][<span class="number">0</span>]=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">            <span class="keyword">int</span>[]current=queue.poll();</span><br><span class="line">            <span class="keyword">int</span> nowX=current[<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">int</span> nowY=current[<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;<span class="number">5</span>;i++)&#123;</span><br><span class="line">                <span class="comment">//四个方向都走一遍试试，看哪个的cost最小</span></span><br><span class="line">                <span class="keyword">int</span> nextX=nowX+direction[i][<span class="number">0</span>];</span><br><span class="line">                <span class="keyword">int</span> nextY=nowY+direction[i][<span class="number">1</span>];</span><br><span class="line">                <span class="keyword">if</span>(nextX&lt;<span class="number">0</span>||nextX&gt;=grid.length||nextY&lt;<span class="number">0</span>||nextY&gt;=grid[<span class="number">0</span>].length)<span class="comment">//下一步出界了</span></span><br><span class="line">                	<span class="keyword">continue</span>;</span><br><span class="line">                <span class="keyword">int</span> cost=count[nowX][nowY]+(grid[nowX][nowY]==i?<span class="number">0</span>:<span class="number">1</span>);</span><br><span class="line">                <span class="comment">//如果我走的方向和格子上的数字不一样，就要花费cost</span></span><br><span class="line">                <span class="keyword">if</span>(cost&lt;count[nextX][nextY])&#123;</span><br><span class="line">                    count[nextX][nextY]=cost;<span class="comment">//更新下一步的cost</span></span><br><span class="line">                    queue.add(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;nextX,nextY&#125;);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">/*for(int i=0;i&lt;count.length;i++)&#123;</span></span><br><span class="line"><span class="comment">            for(int j=0;j&lt;count[i].length;j++)&#123;</span></span><br><span class="line"><span class="comment">                System.out.print(count[i][j]+" ");</span></span><br><span class="line"><span class="comment">            &#125;</span></span><br><span class="line"><span class="comment">            System.out.println();</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">        <span class="keyword">return</span> count[grid.length-<span class="number">1</span>][grid[<span class="number">0</span>].length-<span class="number">1</span>];</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p><strong>leetcode 45/100</strong></p>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls" data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
                <ul id="audio-list" style="display:none">
                    
                        
                            <li title='0' data-url='http://link.hhtjim.com/163/5146554.mp3'></li>
                        
                    
                        
                            <li title='1' data-url='http://link.hhtjim.com/qq/001faIUs4M2zna.mp3'></li>
                        
                    
                </ul>
            
        </div>
        
    <div id='gitalk-container' class="comment link"
        data-ae='false'
        data-ci='c82ee42088349c609c4d'
        data-cs='541eefaa06715f3b1bcd6bf41cb69a4053d18348'
        data-r='PPeony.github.io'
        data-o='PPeony'
        data-a='PPeony'
        data-d='false'
    >查看评论</div>


    </div>
    
</div>


    </div>
</div>
</body>

<script src="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>


<script src="//lib.baomitu.com/jquery/1.8.3/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/diaspora.js"></script>


<link rel="stylesheet" href="/photoswipe/photoswipe.css">
<link rel="stylesheet" href="/photoswipe/default-skin/default-skin.css">


<script src="/photoswipe/photoswipe.min.js"></script>
<script src="/photoswipe/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>




</html>
